//剑指offer52题
//请实现一个函数用来匹配包括'.'和'*'的正则表达式。
//'.'可以表示任意一个字符,'*'表示它前面的字符可以出现任意次(包括0次)。
//eg:
"aaa","a*a" 返回 true
"aaa","ab*a" 返回 false

//思路https://blog.nowcoder.net/n/658d3eae1e014b33a8b9a8d62694de2f?f=comment
//对于'.'没什么复杂的情况，和str[i]==pattern[j]一样，直接i++，j++即可

//问题在于j+1(因为从0开始)为'*'时。
//1,  出现了'*',而且i和j指向的都不相同，那么'*'表示出现了0次 j+2

//2,  出现了'*'，而且i和j指向的相等（这里的相等可以是真正的相等，
//也可以是'.'标记的相等）。比如abcd和ab*cf，其中i和j都指向了b。
//此时应该i+1和j+2。比如abbcd和ab*cf，其中i和j都指向了b。由于b出现了多次
//应该不着急移动p，所以此时i+1即可。比如"cba","cb*a*a"，我也可以认为，
//j指向的第1个a没出现过，即使你相等。因此此时可以s不动，j+2。

 public class Solution{
	public boolean match(char[] str,char[] pattern){
		if(str.length==0&&pattern.length==0){
			return true;
		}
		if(str.length!=0&&pattern.length==0){
			return false;
		}
		return helper(str,0,pattern,0);
	}
	
	public boolean helper(char[] str,int i,char[] pattern,int j){
		if(i==str.length&&j=pattern.length) return true;//递归终止条件
		if(i<str.length&&j=pattern.length) return false;
		
		if(j+1<pattern.length&&pattern[j+1]=='*'){//j+1指向的是'*'时
			if((i<str.length&&str[i]==pattern[j])||
			(i<str.length&&pattern[j]=='.')){//这一步是该题的核心！！！
				return helper(str,i,pattern,j+2)
					   ||helper(str,i+1,pattern,j)
					   ||helper(str,i+1,pattern,j+2);
			}else{
				return helper(str,i,pattern,j+2);
			}
		}
		if(i<str.length&&(str[i]==pattern[j]||pattern[j]=='.')){//j+1指向的不是'*'时
			return helper(str,i+1,pattern,j+1);
		}
		return false;//都不满足，返回false
	}
}